121. 买卖股票的最佳时机
#leetcode#动态规划 2025-01-31

Problem: 121. 买卖股票的最佳时机

解析

考虑在某一天卖出，那么在这一天之前的最小值就是买入的最佳时机，所以只需要遍历一次数组，同时记录最小值和最大利润即可。

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
//!  n,1
class Solution {
 public:
  int maxProfit(vector<int> &prices) {
    int minPrice = prices[0];
    int res = 0;
    for (int i = 1; i < prices.size(); ++i) {
      res = max(res, prices[i] - minPrice);
      minPrice = min(minPrice, prices[i]);
    }
    return res;
  }
};